#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<unordered_map>
using namespace std;

int inf = 1e8;

void solve()
{
    int n, k; cin >> n >> k;
    vector<vector<int>> arr(1005, vector<int>(105, inf)), dp(105, vector<int>(1005, 0));
    for (int i = 1; i <= n; i++)
    {
        int a, b; cin >> a >> b;
        int temp = a + b;
        arr[i][0] = 0;
        for (int j = 1; j <= min(temp, 100); j++)
        {
            if (a == b)
            {
                arr[i][j] = arr[i][j - 1] + a;
                b -= 1;
            }
            else
            {
                if (a > b)
                {
                    arr[i][j] = arr[i][j - 1] + b;
                    a -= 1;
                }
                else
                {
                    arr[i][j] = arr[i][j - 1] + a;
                    b -= 1;
                }
            }
        }
    }
    for (int i = 1; i <= 100; i++) dp[i][0] = inf;
    for (int i = 1; i <= k; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int ans = inf;
            for (int m = 0; m <= i; m++)
            {
                ans = min(ans, dp[i - m][j - 1] + arr[j][m]);
            }
            dp[i][j] = ans;
        }
    }
    if (dp[k][n] >= inf) cout << -1 << endl;
    else cout << dp[k][n] << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}